package org.example.myleet.p567;

public class Solution {
    /**
     * 5 ms
     * 窗口滑动法
     * s1不论怎么排都可以，换句话说只要s2中窗口内字符的频数和s1的相同就行
     * 使用了字符和来起类似哈希的作用，快速知道两个窗口中的字符频数大致上是否相同
     */
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        //sum1和sum2是两个字符窗口的字符和
        int winLen = s1.length(), len2 = s2.length(), sum1 = 0, sum2 = 0;
        //两个字符窗口的字符频数
        int[] freq1 = new int[26];
        int[] freq2 = new int[26];
        for (int i=0; i<winLen; i++) {
            int c1 = s1.charAt(i)-'a';
            ++freq1[c1];
            sum1 += c1;
            int c2 = s2.charAt(i)-'a';
            ++freq2[c2];
            sum2 += c2;
        }
        for (int i=winLen; i<len2; i++) {
            if (sum1 == sum2) {
                //字符和相同的时候才逐一比较s1的频率和s2窗口中字符频数
                boolean similar = isSimilarFreq(freq1, freq2);
                if (similar) {
                    return true;
                }
            }
            //滑窗，出字符，进字符
            int cl = s2.charAt(i-winLen)-'a';
            int cr = s2.charAt(i)-'a';
            --freq2[cl];
            ++freq2[cr];
            //更新s2窗口的字符和
            sum2 += (cr - cl);
        }
        //观察最后一次滑窗的结果
        if (sum1 == sum2) {
            boolean similar = isSimilarFreq(freq1, freq2);
            if (similar) {
                return true;
            }
        }
        return false;
    }

    private boolean isSimilarFreq(int[] freq1, int[] freq2) {
        for (int i = 0; i< 26; i++) {
            if (freq1[i] != freq2[i]) {
                return false;
            }
        }
        return true;
    }
}
